import java.util.ArrayList;
import java.util.Arrays;

/**
 * @version Create on 2012-10-29
 * @author Yinzi Chen
 */

public class CombinationSumII {

	ArrayList<ArrayList<Integer>> res;
	ArrayList<Integer> list;
	int n, num[], target, cnt[], sum;

	public void search(int idx, int depth) {
		if (sum == target) {
			res.add((ArrayList<Integer>) list.clone());
			return;
		}
		if (depth == n || sum + num[idx] > target)
			return;
		int used = 0;
		while (sum <= target && used <= cnt[idx]) {
			search(idx + 1, depth + 1);
			sum += num[idx];
			list.add(num[idx]);
			used++;
		}
		while (list.size() > 0 && used-- > 0) {
			list.remove(list.size() - 1);
			sum -= num[idx];
		}
	}

	public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
		Arrays.sort(num);
		res = new ArrayList<ArrayList<Integer>>();
		list = new ArrayList<Integer>();
		this.num = num;
		this.target = target;
		n = this.num.length;
		cnt = new int[n];
		int j = 0;
		for (int i = 0; i < n;) {
			this.num[j++] = this.num[i++];
			cnt[j - 1] = 1;
			while (i < n && this.num[i] == this.num[i - 1]) {
				i++;
				cnt[j - 1]++;
			}
		}
		n = j;
		sum = 0;
		search(0, 0);
		return res;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
